Глеб устал от побитового исключающего «или» и решил, что пора найти новую интересную функцию. Его выбор пал на медиану. Напомним, медианой массива называется число, которое окажется посередине, если массив упорядочить по возрастанию. В рамках этой задачи для массивов чётной длины положим медиану равной левому из двух центральных в отсортированном порядке элементов.
Для некоторого числа $$$m$$$ назовём $$$m$$$-разбиением массива такое его разбиение на непересекающиеся отрезки, что на каждом из этих отрезков медиана больше либо равна $$$m$$$. Вам дан массив $$$a$$$ длины $$$n$$$ и $$$q$$$ запросов двух видов:
В первой строке дается число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) - размер массива. В следующей строке вводятся $$$n$$$ чисел $$$a_{i}$$$ ($$$1 \le a_{i} \le 10^9$$$) - элементы массива, на следующей строке вводится число $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$) - количество запросов. В следующих $$$q$$$ строках даются запросы, каждый в одном из следующих форматов:
Для каждого запроса второго типа в отдельной строке выведите ответ на запрос. В случае если для отрезка не существует никакого $$$m$$$-разбиения, выведите $$$0$$$.
В задаче присутствуют 6 групп:
5 1 2 3 4 5 4 2 2 1 3 1 1 5 2 5 1 5 2 4 4 5
1 0 2